#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSQRT	(31623)

const int PRULE[] = {0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5};
const int PRU[] = 	{0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0};
const int NEWTON[] ={0, 0, 1, 1, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120};

int checkPrime(int n) {
	int i, j;
	if(n < 2)
		return 0;
	for(i = n - 1; i > 1; i--) {
		if(n % i == 0) {
			return 0;	//isn't prime
		}
	}
	return 1; //is prime
}

int pow2(int n) {
	if(n < 1)
		return 1;
	return pow2(n -1) * 2;
}

int checkNumber(int n, int k) {
	int w, i, j, m, ret, r;
	m = 1; //for div by 1
	r = 0;
	for(i = MAXSQRT; i > 1; i--) {
		w = 0;
		if(n % i == 0) {
			if(checkPrime(i) == 1) {
				while(n % i == 0) {
					n = n / i;
					w++;
				}
			}
		}
		m += PRULE[w];
		r += PRU[w];
	}
	if(n > 1)
		m++;
	m += NEWTON[r];
	return m >= k ? 1 : 0;
}

int main() {
	int t, n, k, i, j;
	scanf("%d", &t);

	while(t--) {	
		scanf("%d %d", &n, &k);	
		if(checkNumber(n, k) == 1)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	
	return 0;
}
